/*
 * divide.cpp
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */

#include "BigInt.h"
#include <assert.h>
using namespace APIAL;

void APIAL::Divide(BigInt* left, BigInt* right, BigInt* result) {
	
	// check alias
	assert(left  != result);
	assert(right != result);

	// normalize the left and right
	BigInt::normalize(*left);
	BigInt::normalize(*right);

	// OPTIMIZATION: If divisor is larger than dividend, result is 0
	if (left->size < right->size) {
		if (result->capacity < 1)
			result->resize(1, false);
		result->size = 1;
		result->chunks[0] = 0;
		result->positive = true;
		return;
	}

	// Divide operation: dividend / divisor = quotient
	BigInt* divisor = new BigInt(*right);
	BigInt* dividend = new BigInt(*left);
	bool pos = true;
	if ((divisor->positive == true && dividend->positive == false) || (dividend->positive && divisor->positive == false))
		pos = false;
	divisor->positive = true;
	dividend->positive = true;
	int result_size = dividend->size;
	if (result->capacity < result_size)	// <-- Resize result if needed
		result->resize(result_size, false);
	result->size = 1;
	result->chunks[0] = 0x0;
	BigInt* scratchData = new BigInt(result_size);

	// Find the leading 1 bit in the dividend and divisor
	int dividendbit = dividend->nonCarryBits - 1;
	int divisorbit = divisor->nonCarryBits - 1;
	while (!(dividend->chunks[dividend->size - 1] & (1 << dividendbit)))
		dividendbit--;
	while (!(divisor->chunks[divisor->size - 1] & (1 << divisorbit)))
		divisorbit--;

	// Set values for the length of significant bits in divisor and dividend
	int divisorlength = (divisor->size - 1) * divisor->nonCarryBits + divisorbit + 1;
	int dividendlength = (dividend->size - 1) * dividend->nonCarryBits + dividendbit + 1;

	// Shift the divisor
	LeftShift(divisor, dividendlength - divisorlength, divisor);

	// Set max iterations
	int totalloops = dividendlength - divisorlength + 1;

	// Loop: go through the dividend chunks
	for (int dividendchunk = dividend->size-1; dividendchunk >=divisor->size - 1; dividendchunk--) {

		// Loop: go through the dividend bits, if less than subtract and add 1 to left shift
		for (; dividendbit >= 0 && totalloops > 0; dividendbit--, totalloops--) {

			// always shift left one
			LeftShift(result, 1, result);
			result->size = result->size?result->size:1;

			// if lessthan, subtract and or a one in (note had to use not greater than)
			if (!(*dividend < *divisor)) {
				
				// subtract and shift
				Subtract(dividend, divisor, dividend, scratchData);
				
				result->chunks[0] = result->chunks[0] | 1;
			}

			RightShift(divisor, 1, divisor);
		}

		// increase dividendbit for next chunk
		dividendbit = dividend->nonCarryBits - 1;
	}
	if (pos == false)
		result->positive = false;
}
